//
//  main.c
//  TradeMoney-货币最少支付算法
//
//  Created by zhuoooo on 2022/6/22.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//  https://blog.csdn.net/Tink_bell/article/details/80785423

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000

int MinMoney(int n, int arraydemo[], int y);//货币支付最少算法

int main(int argc, const char * argv[]) {
    int n, y, k;
    int arraydemo[MAX] = {0};
    printf("请输入货币面值种类n及要支付的价格y: \n");
    scanf("%d%d", &n, &y);
    printf("请依次输入%d种货币的面值: \n", n);
    for(k = 0; k <n; k++)
    {
        scanf("%d", &arraydemo[k]);
    }
    
    int minNumber = MinMoney(n, arraydemo, y);
    
    printf("支付%d所需的最少货币张数为: %d\n", y, minNumber);
    
    return 0;
}

int MinMoney(int n, int arraydemo[], int y)
{
    int dp[n+1][y+1], i, j;//定义存放动态规划子问题解的表格
    int minNumber = MAX;
    if(n <= 0 || y < 0)
    {
        return -1;
    }
    
    for(i = 0; i <= n; i++)//初始化
    {
        dp[i][0] = 0 ;
    }
    for(j = 0; j <= y; j++)
    {
        dp[0][j] = 1000;
        
    }
    
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= y; j++)
        {   //1、判断支付金额是否大于等于当前硬币的面值，如果大于等于那么可以支付，否则为子问题的解
            //2、如果可以支付，判断子问题的解和使用该面值后的硬币数  谁少取谁
            if(dp[i-1][j] < dp[i][j-arraydemo[i-1]]+1)
            {
                dp[i][j] = dp[i-1][j];
            }
            else
            {
                dp[i][j] = dp[i][j-arraydemo[i-1]]+1;
            }
            if(dp[i][j] < minNumber)
            {
                minNumber = dp[i][j];
            }
        }
    }
    
    return dp[n][y];
    
}
